class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 先排升序
        sort(nums.begin(), nums.end());
        int cnt = 0, n = nums.size();

        // 先固定最长的边c
        for(int c = n - 1; c >= 2; c--) // 最后一组是 c == 2
        {
            for(int a = 0, b = c - 1; a != b; )
            {
                if(nums[a] + nums[b] > nums[c])
                {
                    cnt += b - a;   // 有效三角形个数为 a,b区间的间隔
                    b--;            // 判断完一组 b--
                }
                else
                {
                    a++;            // 无效的三角形 a++
                }
            }
        }

        return cnt;
    }
};